This study is designed to determine whether Bacillus Calmette Guerin (BCG), a bovine tubercle germ in combination with melanoma vaccine (C-VAX) is more effective than BCG and a placebo in stimulation of an immune response against melanoma, in improving overall survival, and increasing a delay in recurrence following surgery. This research is being done because there is no currently approved treatment of melanoma, which prolongs the time to recurrence. It is hoped that C-VAX, an experimental vaccine, will have benefits, which will help alleviate this problem.